/**************************************************************
          File Name:heap_sort.c
          Author: Abby Cin
          Mail: abbytsing@gmail.com
          Created Time: 2015-04-13 21:31:09
***************************************************************/

#include<stdio.h>
#include<stdlib.h>

static int my_size;

int l_child(int idx)
{
    return idx*2;
}

int r_child(int idx)
{
    return idx*2 + 1;
}

int parent(int idx)
{
    return idx / 2;
}

void to_heap(int A[], int n)
{
    int lc, rc, largest, tmp;

    lc = l_child(n);
    rc = r_child(n);

/* compare with A.length, if left child larger
 * than parent, then assign left child to largest
 * else initail largest to parent*/
 
    if(lc <= my_size && A[lc] > A[n]) 
        largest = lc;
    else
        largest = n;
/* now compare parent with right child, to find the larger
 * one then assign to largest */
    if(rc <= my_size && A[rc] > A[largest])
        largest = rc;
/* i.e. one of children is larger than parent. then exchange
 * values between child and parent, finally search the larger
 * child of current child, reapt the same operation till the 
 * top of this heap */
    if(largest != n) 
    {
        tmp = A[n];
        A[n] = A[largest];
        A[largest] = tmp;
        to_heap(A, largest);
    }
}

void make_heap(int A[])
{
    int i;
/* get floor of half array, this is the root of heap
 * then expanding to top leaves, and make each of node 
 * satisfy the heap difinition by calling to_heap() for
 * each parent node */
    for(i = my_size / 2; i >= 0; i--)
        to_heap(A, i);
}

void heap_sort(int A[])
{
    int i, tmp;

    make_heap(A);

    for(i = my_size; i >= 1; i--)
    {
        tmp = A[0];
        A[0] = A[i];
        A[i] = tmp;
        my_size -= 1;
        to_heap(A, 0);
    }
}

int main(int argc, char *argv[])
{
    if(argc != 2)
    {
        fprintf(stderr, "%s length(how many elements in array to create)\n", argv[0]);
        exit(1);
    }

    my_size = atoi(argv[1]);
    int A[my_size], i, length;
    length = my_size;

    for(i = 0; i < my_size; i++)
        A[i] = rand();

    heap_sort(A);
/*
    for(i=0; i< length; i++)
        printf("%d ", A[i]);
    putchar('\n');
*/
    return 0;
}
